home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / follow.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  3KB  |  143 lines
  1. /* the functions in this file take a syntax tree for a regular
  2.    expression and produce a DFA using the McNaughton-Yamada
  3.    construction.                        */
  4.  
  5. #include <stdio.h>
  6. #include "re.h"
  7.  
  8. extern char *strncpy(), *strcat(), *strcpy();
  9. extern int  strlen();
  10.  
  11. #define TRUE    1
  12.  
  13. extern char *malloc();
  14. extern Pset pset_union(); 
  15. extern int pos_cnt;
  16. extern Re_node parse();
  17.  
  18. Re_lit_array lpos; 
  19.  
  20.  
  21. /*  extend_re() extends the RE by adding a ".*(" at the front and a "("
  22.     at the back.                               */
  23.  
  24. char *extend_re(s)
  25. char *s;
  26. {
  27.     char *s1;
  28.  
  29.     s1 = malloc((unsigned) strlen(s)+4+1);
  30.     return strcat(strcat(strcpy(s1, ".*("), s), ")");
  31. }
  32.  
  33. /* mk_followpos() takes a syntax tree for a regular expression and
  34.    traverses it once, computing the followpos function at each node
  35.    and returns a pointer to an array whose ith element is a pointer
  36.    to a list of position nodes, representing the positions in
  37.    followpos(i).                            */
  38.  
  39. void mk_followpos_1(e, fpos)
  40. Re_node e;
  41. Pset_array fpos;
  42. {
  43.     Pset pos;
  44.     int i;
  45.  
  46.     switch (Op(e)) {
  47.     case EOS: break;
  48.     case OPSTAR:
  49.         pos = Lastpos(e);
  50.         while (pos != NULL) {
  51.         i = pos->posnum;
  52.         (*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i]);
  53.         pos = pos->nextpos;
  54.         }
  55.         mk_followpos_1(Child(e), fpos);
  56.         break;
  57.     case OPCAT:
  58.         pos = Lastpos(Lchild(e));
  59.         while (pos != NULL) {
  60.         i = pos->posnum;
  61.         (*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i]);
  62.         pos = pos->nextpos;
  63.         }
  64.         mk_followpos_1(Lchild(e), fpos);
  65.         mk_followpos_1(Rchild(e), fpos);
  66.         break;
  67.     case OPOPT:
  68.         mk_followpos_1(Child(e), fpos);
  69.         break;
  70.     case OPALT:
  71.         mk_followpos_1(Lchild(e), fpos);
  72.         mk_followpos_1(Rchild(e), fpos);
  73.         break;
  74.     case LITERAL:
  75.         break;
  76.     default: printf("mk_followpos: unknown node type %d\n", Op(e));
  77.     }
  78.     return;
  79. }
  80.  
  81. Pset_array mk_followpos(tree, npos)
  82. Re_node tree;
  83. int npos;
  84. {
  85.     int i;
  86.     Pset_array fpos;
  87.  
  88.     if (tree == NULL || npos < 0) return NULL;
  89.     fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));
  90.     if (fpos == NULL) return NULL;
  91.     for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;
  92.     mk_followpos_1(tree, fpos);
  93.     return fpos;
  94. }
  95.  
  96. /* mk_poslist() sets a static array whose i_th element is a pointer to
  97.    the RE-literal at position i.  It returns 1 if everything is OK,  0
  98.    otherwise.                                */
  99.  
  100. /* init performs initialization actions; it returns -1 in case of error,
  101.    0 if everything goes OK.                        */
  102.  
  103. int init(s, table)
  104. char *s; int table[32][32];
  105. {
  106.     Pset_array fpos;
  107.     Re_node e;
  108.     Pset l;
  109.     int i, j;
  110.  
  111.     if ((e = parse(extend_re(s))) == NULL) return -1;
  112.     if ((fpos = mk_followpos(e, pos_cnt)) == NULL) return -1;
  113.     for (i = 0; i <= pos_cnt; i += 1) {
  114. #ifdef Debug
  115.     printf("followpos[%d] = ", i);
  116. #endif
  117.         l = (*fpos)[i];
  118.         j = 0;
  119.         for ( ; l != NULL; l = l->nextpos)  {
  120. #ifdef Debug
  121.             printf("%d ", l->posnum);
  122. #endif
  123.             table[i][j] = l->posnum;
  124.             j++;
  125.         } 
  126. #ifdef Debug
  127.         printf("\n");
  128. #endif
  129.     }
  130. #ifdef Debug
  131.     for (i=0; i <= pos_cnt; i += 1)  {
  132.        j = 0;
  133.        while (table[i][j] != 0) {
  134.           printf(" %d ", table[i][j]);
  135.           j++;
  136.       }
  137.       printf("\n");
  138.    }
  139. #endif
  140.     return (pos_cnt);
  141. }
  142.  
  143.